/* 
 * CMPS 258: Programming Languages
 *        Assignment 2 - Part2: "Spy" - March 24, 2008
 *        Group name: Doomsday
 *        Authors:  Ramsey Nasser (ID# 200600496) 
 *                  Hadi Abu Rislan (ID# 200600426) 
 *                  Kevin Azzam (ID# 200602033)
 * 
 * Implementation of path data structure and related functions.
 * 
 * For the sake of maintainability, function documentation is not repeated
 * here. For a description of the intent and usage of each function, refer to
 * the header file (graph.h) 
 */
#include <stdlib.h>
#include <stdio.h>

#include "util.h"
#include "graph.h"
#include "path.h"

path* path_init(graph* g, int root) {
	path* p;
	allocatep(p);
	
	p->root = root;
	p->size = 0;
	p->graph = g;
	p->steps = NULL;
	
	return p;
}

path* path_clone(path* p) {
	int i;
	path* new_path = path_init(p->graph,p->root);
	
	if(p->steps) {
		// Loop through steps of path p and append them to new_path
		for(i=0;i<p->size;i++)
			path_append(new_path,p->steps[i]->to->id);
	}
	
	return new_path;
}

BOOL path_contains(path* p, int v) {
	int i;
	for(i=0;i<p->size;i++)
		if(p->steps[i]->from->id == v || p->steps[i]->to->id == v)
			return TRUE;
	return FALSE;
}

BOOL path_append(path* p, int v) {
	// Is this the first step? Is the last step of the path connected vertex v?
	if(p->size==0 || graph_are_connected(p->graph,p->steps[p->size-1]->to->id,v)) {
		// They are, so the next step, v, is valid
		if(!p->steps) {
			// first call
			allocateg(p->steps,p->size);
			p->steps[0] = graph_get_edge(p->graph,p->root,v);
		} else {
			// subsequent calls
			allocateg(p->steps,p->size);
			p->steps[p->size-1] = graph_get_edge(p->graph,p->steps[p->size-2]->to->id,v);
		}
		
		return TRUE;
	} else
		// They are not, so the next step, v, is invalid
		return FALSE;
}

void path_print(path* p) {
	int i;
	printf("%d",p->steps[0]->from->id);
	for(i=0;i<p->size;i++)
			printf(" -> %d",p->steps[i]->to->id);
	printf("\n");
}

BOOL path_is_broken(path* p) {
	int i;
	for(i=0;i<p->size;i++)
		if(p->steps[i]->broken)
			return TRUE;
	return FALSE;
}

edge* path_get_most_frequent_step(path* p) {
	int i;
	edge* freq_step = NULL;
	for(i=0;i<p->size;i++)
		if(!freq_step || p->steps[i]->freq > freq_step->freq)
			freq_step = p->steps[i];
	return freq_step;
}
